leetcode-53. 最大子数组和

53. 最大子数组和

解法

1. 第一版写的时候，可以加一个 dp 数组，保存每个节点的最大值

dp 公式

class Solution {
    
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function maxSubArray($nums) {
        $len = count($nums);
        if ($len == 1) {
            return $nums[0];
        }
        
        $currentMaxSum = $nums[0];
        
        $max = $nums[0];
        for ($i=1; $i < $len; $i++) {
            $currentMaxSum = max($currentMaxSum + $nums[$i], $nums[$i]);
            $max = max($currentMaxSum, $max);
        }
        
        return $max;
    }
}

2024-10-31

使用go语言重新写一遍，仍然是dp思想

该算法的核心思想是求 “以当前位置为结尾的最大子数组和”

func maxSubArray(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    winSum := 0
    mxSum := nums[0]

    for i := range nums {
	    winSum = max(nums[i], nums[i]+winSum)
        mxSum = max(mxSum, winSum)
    }

    return mxSum
}